/*
 * hashmap.h 
 * Copyright (c) 2009 Vedant Kumar <vminch@gmail.com>
 * 		- with thanks to nvteighen and tinivole of ubuntuforums.org
 * 
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef AL_MAP_H
#define AL_MAP_H

#define MAP_PRESET_SIZE 	(2 << 6) // use a power of 2 for faster array access
#define MAP_GROWTH_RATE 	2

#define HMAP_MAKE_HASHFN	// build a few hash functions 
#define MAP_DESTRUCTORS	// require destructors for value clean-up
#ifdef HMAP_MAKE_HASHFN
#include <string.h>
#endif
#define MAP_MAX_CAPACITY 1073741824l
#define MAP_MAX_THRESHOLD 2147483647l
#include <stdlib.h>
#include "collection.h"

typedef struct map_fn {
	hash_fn hash_key_fn;
	eq_fn eq_key_fn;
	del_fn del_key_fn;
	del_fn del_val_fn;
} map_fn;
typedef struct hash_entry hash_entry;
typedef struct hashmap hashmap;
#define HASH_MAP_ENTRY_FIELDS() \
	hash_entry *next; \
	object k; \
	object v; \
	hash_t hash;

struct hash_entry {
	HASH_MAP_ENTRY_FIELDS()
	;
};

#define HASH_MAP_FIELDS() \
	mem_storage *storage; \
	mem_type type; \
	hash_entry** table; \
	uint32_t size; \
	uint32_t threshold; \
	uint32_t capacity; \
	map_fn fns;

struct hashmap {
	HASH_MAP_FIELDS()
	;
};


/**********************Hash Map API*******************************/
// create a hashmap
extern hashmap* hmap_new(map_fn *fns, mem_storage *storage, mem_type type);

#define index_forhash(hash, tablen) (hash & (tablen - 1))

// delete the hashmap (and if destructors are enabled, destroy all values)
extern void hmap_free(hashmap* hmap);

extern void hmap_clear(hashmap* hmap, bool del);

// add a value (with a given key) to the hashmap
extern object __hmap_put(hashmap* hmap, object k, object v);
#define hmap_put(hmap, k, v) __hmap_put(hmap, (object) k, (object) v)

// retrieve a value using a given key from the hashmap
// returns your value if successful and NULL if not
extern object __hmap_get(hashmap* hmap, object k);
#define hmap_get(hmap, obj) __hmap_get(hmap, (object) obj)
extern object __hmap_remove(hashmap *hmap, object k);
#define hmap_remove(hmap, obj) __hmap_remove(hmap, (object) obj)

/********************Hash Map API END*********************************/

/********************Linked Hash Map API*******************************/
typedef struct linked_entry linked_entry;

struct linked_entry {
	HASH_MAP_ENTRY_FIELDS()
	;
	linked_entry *before;
	linked_entry *after;
};

typedef struct linkedmap {
	HASH_MAP_FIELDS()
	;
	linked_entry *header;
	bool access_order;
} linkedmap;

/**
 * get oldest entry of a given linkedmap if map not empty otherwise return NULL
 *
 */
#define LMAP_GET_ELDEST_ENTRY(map) ((map)->size ? (map->header->after) : NULL)
#define lmap_entry_remove_link(entry) { \
	(entry)->before->after = (entry)->after; \
	(entry)->after->before = (entry)->before; \
}

#define lmap_entry_add_before(src, dst) { \
	(src)->after = (dst); \
	(src)->before = (dst)->before; \
	(src)->before->after = (src); \
	(src)->after->before = (src); \
}

#define lmap_record_access(map, entry) { \
	lmap_entry_remove_link(entry); \
	lmap_entry_add_before(entry, map->header); \
}

extern linkedmap * lmap_new(map_fn *fn, bool access_order,
		mem_storage *storage, mem_type type);
/*free all data entry which a given hashmap links to. It free itself too*/
extern void lmap_free(linkedmap *map);
extern void lmap_clear(linkedmap *map, bool del);
extern object lmap_put(linkedmap *map, object k, object v);
extern object lmap_put1(linkedmap *map, object k, object v, bool access_order);
extern object lmap_get(linkedmap *map, object k);
extern object lmap_get1(linkedmap *map, object k, bool access_order);
extern linked_entry *lmap_get_entry(linkedmap* map, object k);
extern linked_entry
* lmap_get_nextentry(linkedmap *map, linked_entry *cur_entry);
extern linked_entry *lmap_entry_deattach(linkedmap *map, linked_entry *en);
extern linked_entry *lmap_add_entry_head(linkedmap *map, linked_entry *en);
extern void* lmap_remove(linkedmap *map, object k);

/*************************Linked Hash Map API END****************************/

/**********************Concurrent Hash Map API*******************************/
#define MAP_DEFAULT_CONCURRENCY_LEVEL 16
#define MAP_MAX_SEGMENTS 1 << 16
#define RETRIES_BEFORE_LOCK 2

typedef struct concurr_entry concurr_entry;
struct concurr_entry {
	concurr_entry* volatile next;
	object k;
	hash_t hash;
	object volatile v;
};

typedef struct segment {
	pthread_mutex_t lock;
	/**
	 * The number of elements in this segment's region.
	 */
	volatile int count;

	/**
	 * Number of updates that alter the size of the table. This is
	 * used during bulk-read methods to make sure they see a
	 * consistent snapshot: If modCounts change during a traversal
	 * of segments computing size or checking containsValue, then
	 * we might have an inconsistent view of state so (usually)
	 * must retry.
	 */
	int mod_count;

	/**
	 * The table is rehashed when its size exceeds this threshold.
	 * (The value of this field is always <tt>(int)(capacity *
	 * loadFactor)</tt>.)
	 */
	int threshold;

	/**
	 * The per-segment table.
	 */
	volatile concurr_entry** volatile table;

	concurr_entry **free_entries;
	int free_size;
} segment;

typedef struct concurrentmap {
	map_fn fns;
	/**
	 * Mask value for indexing into segments. The upper bits of a
	 * key's hash code are used to choose the segment.
	 */
	int segm_mask;

	/**
	 * Shift value for indexing within segments.
	 */
	int segm_shift;

	/**
	 * The segments, each of which is a specialized hash table
	 */
	segment* segms;
} concurrentmap;

extern concurrentmap * cmap_new(map_fn *fn, int capacity, int concurr_lvl);

/**
 * Maps the specified key to the specified value in this table.
 * Neither the key nor the value can be null.
 *
 * <p> The value can be retrieved by calling the <tt>get</tt> method
 * with a key that is equal to the original key.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 */
extern object cmap_put(concurrentmap *map, object k, object v);

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code key.equals(k)},
 * then this method returns {@code v}; otherwise it returns
 * {@code null}.  (There can be at most one such mapping.)
 *
 */
extern object cmap_get(concurrentmap* map, object k);

/*
 If the specified key is not already associated with a value, associate it with the given value. This is equivalent to

 if (!map.containsKey(key))
 return map.put(key, value);
 else
 return map.get(key);

 except that the action is performed atomically.
 Specified by: putIfAbsent(...) in ConcurrentMap

 Parameters:
 key key with which the specified value is to be associated
 value value to be associated with the specified key
 Returns:
 the previous value associated with the specified key, or null if there was no mapping for the key*/
extern object cmap_put_absent(concurrentmap *map, object k, object v);

/*Replaces the entry for a key only if currently mapped to some value. This is equivalent to

 if (map.containsKey(key)) {
 return map.put(key, value);
 } else return null;

 except that the action is performed atomically.
 Specified by: replace(...) in ConcurrentMap

 Parameters:
 key key with which the specified value is associated
 value value to be associated with the specified key
 Returns:
 the previous value associated with the specified key, or null if there was no mapping for the key*/
extern object cmap_replace(concurrentmap *map, object k, object v);

/**
 * Removes the key (and its corresponding value) from this map.
 * This method does nothing if the key is not in the map.
 *
 * @param  key the key that needs to be removed
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 */
extern object cmap_remove(concurrentmap *map, object k, object *orga_key);

extern void cmap_clear(concurrentmap *map, bool del);

extern void cmap_free(concurrentmap *map);
/**********************Concurrent Hash Map API END*******************************/

#ifdef HMAP_MAKE_HASHFN
// integer-as-key hash functions
hash_t int_hash_fn(object);
bool int_eq_fn(object, object);
void int_del_fn(void *value);

// char*-as-key hash functions
hash_t str_hash_fn(object);
bool str_eq_fn(object, object);
void str_del_fn(void *value);
#endif

#endif
